#include <bits/stdc++.h>
#include "../../tools/tools.h"
using namespace std;


class Solution {
public:
    int numberOfSubmatrices(vector<vector<char>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector preX(n + 1, vector(m + 1, 0));
        vector preY(n + 1, vector(m + 1, 0));

        int ans = 0;
        for(int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; ++j) {
                preX[i][j] = preX[i - 1][j] + preX[i][j - 1] - preX[i - 1][j - 1] + (grid[i - 1][j - 1] == 'X' ? 1 : 0);
                preY[i][j] = preY[i - 1][j] + preY[i][j - 1] - preY[i - 1][j - 1] + (grid[i - 1][j - 1] == 'Y' ? 1 : 0);
                if(preX[i][j] > 0 && preX[i][j] == preY[i][j]) ans++;
            }
        }
        return ans;
    }
};

int main(int argc, const char** argv) {
    // debug();
    return 0;
}
